package datastructure.link;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/28 9:27
 * @Description
 */
public class Leet21 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null&&list2==null){
            return null;
        }
        ListNode temp = new ListNode(-101);
        ListNode res = temp;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2= list2.next;
            }
            temp = temp.next;
        }
        if(list1==null){
            temp.next = list2;
        }
        if(list2==null){
            temp.next = list1;
        }
        return res.next;
    }

    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if(list1==null&&list2==null){
            return null;
        }
        ListNode res = new ListNode();
        test(res,list1,list2);
        return res.next;
    }

    public void test(ListNode temp ,ListNode list1, ListNode list2){

        if(list1==null){
            temp.next = list2;
            return ;
        }
        if(list2==null){
            temp.next = list1;
            return ;
        }
        if(list1.val<=list2.val){
            temp.next = list1;
            test(temp.next, list2.next,list2);
        }else{
            temp.next = list2;
            test(temp.next, list1.next,list1);
        }
    }
}
